from __future__ import generators
import os,sys,sets,random,logging
from pprint import pprint

from networkx.digraph import DiGraph

from posnet_handlers import * # import all handlers

algorithms = {  "first_fit (Point query)":first_fit_point_query_handler,\
		"first_fit2 (Point query)":first_fit2_point_query_handler,\
		"all_fit (Point query)":all_fit_point_query_handler,\
		"all_parents (Point query)":all_parents_point_query_handler, \
		"all_children (Point query)":all_children_point_query_handler, \
		"all_top (Point query)":all_top_point_query_handler, \
		"parents (Point query)":parents_point_query_handler, \
		"exact (Point query)":exact_point_query_handler, \
		"all_match (Range query)":all_match_range_query_handler  }  

Relations = {"c2p":"parents", "p2c" : "childs","p2p":"peers"}
Relations_sym = {"c2p":"p2c", "p2c":"c2p","p2p":"p2p"}

# a semantic graph with info
class posnet_local_semantic_graph(object):
	def __init__(self,poset):
		object.__init__(self) #,poset)
		self._poset = dict()
		self._poset_keys = [] #self._poset.keys()
		poset_keys = poset.keys()
		poset_keys.sort()
		for k in poset_keys:
			self.add_poset_key(k, poset[k] )
		#self._poset_keys.sort()
		self._graph = DiGraph() # internal semantic graph structure
		self._top = sets.Set() # top nodes in this graph (nodes that have at least one p2p edges and no outgoing c2p link)
		self._data = dict() # keep track of neighbor data for each semantic node
		self._space_point_to_vertex_id = dict()
		self._vertex_id_to_space_point = []
		self._links = dict() # map from vertex tuples to relation
		self._media = None # the overlay node that maitain info on graph nodes => if a node is external, a query will be pushed out from this graph
	def has_poset_key(self,key):
		for kk in self._poset_keys:
			if kk == key or kk[1] == key: return True
		else: return False 

	def add_poset_key(self,key,vals = None):
		if type(key) == type( (1,2) ):
			key = key[-1]
		if not self.has_poset_key(key):
			self._add_poset_key_nocheck(key,vals)	

	def _add_poset_key_nocheck(self,key,vals = None):
		l = len(self._poset_keys)
		k = (l,key)
		if vals is None: vals  = []
		self._poset[k] = vals
		self._poset_keys.append(k)
		self._poset_keys.sort()

	def get_link_type(self,src,dst):
		dat = self._data[src]
		if dst in dat["childs"]: return "p2c"
		elif dst in dat["peers"]: return "p2p"
		elif dst in dat["parents"]: return "c2p" 
		else:
			datt = self._data[dst]
			if src in datt["childs"]: return "c2p"
			elif src in datt["peers"]: return "p2p"
			elif src in datt["parents"]: return "p2c"
			

	def data(self,node_id = None):
		if node_id is not None: return self._data[node_id]
		else: return self._data
	#def graph(self): return self._graph
	def set_media(self,onode): self._media = onode
	def poset(self): return self._poset
	def __len__(self): return len(self._space_point_to_vertex_id)
	def __str__(self):
		import StringIO
		out  = StringIO.StringIO()
		print >>out,"greph.nodes:",self._graph.nodes()
		print >>out,"greph.space_points:",self._vertex_id_to_space_point
		print >>out,"greph.vertex_id:",self._space_point_to_vertex_id
		print >>out,"greph.edges:",self._graph.edges()
		print >>out,"graph.relations:",self._links
		return out.getvalue()
	def n_nodes(self): return len(self._graph)
	def random_node(self):
		return self._graph.nodes()[random.choice(range(0,len(self._graph))) ]
	def random_space_point(self):
		return self.space_point(self.random_node()) 
		
	def vertex_id(self,space_point):
		""" return the node id from its description (if exist in this semantic graph)"""
		space_point_copy = self.hashable_space_point(space_point)
		if self._space_point_to_vertex_id.has_key(space_point_copy):
			return self._space_point_to_vertex_id[space_point_copy]
		else: raise Exception("node not found with description: "+str(space_point))
	def get_vertex_id_dict(self):
		return self._space_point_to_vertex_id
	
	def space_point_table(self,space_point):
		ty = type( space_point)  
		if ty == type( (1,2) ): return [x for x in  space_point]
		elif ty == type( [] ): return space_point
		else:
			try:#print type(space_point),space_point
				return [ space_point[x[-1]]  for x in self._poset_keys ]
			except Exception,e:
				print "poset keys",self._poset_keys
				print >>sys.stderr,"Error while trying to convert point to table: "+str(space_point)
				from traceback import print_exc
				print_exc()
				sys.stderr.flush()
				raise

	def hashable_space_point(self,space_point):
		ty = type( space_point)  
		if ty == type( (1,2) ): return space_point
		elif ty == type( [] ):
			space_point_copy = ()
			for x in space_point: space_point_copy += x,
			return space_point_copy 
		else:
			space_point_copy = ()
			try:
				for x in self._poset_keys: space_point_copy += space_point[x[-1]],
				return space_point_copy 
			except:
				print >>sys.stderr,"semantic_graph: error while treating space point",space_point
				raise
	def space_point(self,vertex_id):
		""" return the node id from its description (if exist in this semantic graph)"""
		ret = None
		if len(self._vertex_id_to_space_point) > vertex_id:
			ret = self._vertex_id_to_space_point[vertex_id]
		if ret is None: raise Exception("node not found with vertex_id: "+str(vertex_id))
		return ret
	

	def add_node(self,space_point):
		""" add a vertex in semantic graph if not exist for this data descrption""" 
		vertex_id = None
		space_point_copy = self.hashable_space_point(space_point)
		if self._space_point_to_vertex_id.has_key(space_point_copy):
			vertex_id = self._space_point_to_vertex_id[space_point_copy]
		else:
			vertex_id = len(self._vertex_id_to_space_point)
			self._space_point_to_vertex_id[space_point_copy] = vertex_id
			self._vertex_id_to_space_point.append(space_point)
			self._graph.add_node(vertex_id)
			self._data[vertex_id] = dict()
			self._data[vertex_id]["space_point"] = space_point
			self._data[vertex_id]["neighbors"] = dict()
			self._data[vertex_id]["parents"] = []
			self._data[vertex_id]["childs"] = []
			self._data[vertex_id]["peers"] = []
			#logging.debug("add vertex to graph : "+str(vertex_id)+" -> "+str(space_point))
		return vertex_id

	def remove_node(self,vertex_id):
		space_point = self._vertex_id_to_space_point[vertex_id]
		space_point_copy = self.hashable_space_point(space_point)
		space_point = space_point_copy
		if self._space_point_to_vertex_id.has_key(space_point):
			vertex_id = self._space_point_to_vertex_id[space_point]
			edge_to_del = [(pred,vertex_id) for pred in self._graph.predecessors(vertex_id)]
			edge_to_del.extend([(vertex_id,suc) for pred in self._graph.successors(vertex_id)])
			for edge in edge_to_del:
				s,t = edge
				self.remove_edge(s,t)
			self._graph.delete_node(vertex_id)
			self._vertex_id_to_space_point[vertex_id] = None
			del self._data[vertex_id]
			del self._space_point_to_vertex_id[space_point]

	def add_edge(self,vertex_id1,vertex_id2,relation,relation_sym,bidir = None):
		if bidir is None: bidir = True
		relation_name = Relations[relation]
		relation_sym_name = Relations[relation_sym]
		if not self._graph.has_edge(vertex_id1,vertex_id2):
			self._graph.add_edge(vertex_id1,vertex_id2)
			if not self._data[vertex_id1].has_key(relation_name): self._data[vertex_id1][relation_name] =[vertex_id2]
			else: self._data[vertex_id1][relation_name].append(vertex_id2)
			self._links[(vertex_id1,vertex_id2)] = relation
			self._data[vertex_id1]["neighbors"][vertex_id2] = self._vertex_id_to_space_point[vertex_id2]
			self._data[vertex_id2]["neighbors"][vertex_id1] = self._vertex_id_to_space_point[vertex_id1]
			if bidir:
				self._graph.add_edge(vertex_id2,vertex_id1)
				if not self._data[vertex_id2].has_key(relation_sym_name): self._data[vertex_id2][relation_sym_name] =[vertex_id1]
				else: self._data[vertex_id2][relation_sym_name].append(vertex_id1)
				self._links[(vertex_id2,vertex_id1)] = relation_sym

	def remove_edge(self,vertex_id1,vertex_id2):
		#print "* BEFORE REMOVE"
		#pprint(self._data)
		self.remove_edge_unidir(vertex_id1,vertex_id2)
		self.remove_edge_unidir(vertex_id2,vertex_id1)
	def remove_edge_unidir(self,vertex_id1,vertex_id2):
		#print "* BEFORE REMOVE"
		#pprint(self._data)
		if self._graph.has_edge(vertex_id1,vertex_id2):
			self._graph.delete_edge(vertex_id1,vertex_id2)
			relation =  Relations[self._links[(vertex_id1,vertex_id2)]]
			del self._links[(vertex_id1,vertex_id2)]
			tab = [x for x in self._data[vertex_id1][relation] if x != vertex_id2]
			self._data[vertex_id1][relation] = tab
			del self._data[vertex_id1]["neighbors"][vertex_id2]
			
		#print "* AFTER REMOVE"
		#pprint(self._data)

	def degree(self,vertex_id):
		return len(self._data[vertex_id]["neighbors"])

#	def inject(self,space_point_source,space_point_target,query):
#		vertex_id_s = self.vertex_id(space_point_s)
#		vertex_id_t = self.vertex_id(space_point_t)
#		query.source = vertex_id_s
#		query.target = vertex_id_t
#		self.receive(query)	
#
#	def receive(self,query):
#		algorithm = query.query_type
#		last_node = query.source
#		this_node = query.target
#		self.process_query(last_node,this_node,last_link,algorithm,query.data)

	def process_query(self,receiver,algorithm,request_to_treat,sender = None):
		link_type = ""
		if sender is not None: link_type = self.get_link_type(sender,receiver)
		query_handler = algorithms[algorithm] # find from algorithm
		if algorithm.find("(Point query)") > -1 and request_to_treat is not None:
			request_to_treat = self.space_point_table(request_to_treat)
		elif algorithm.find("(Range query)") > -1 and request_to_treat is not None:
			first_point =  self.space_point_table(request_to_treat[0]) 
			second_point =  self.space_point_table(request_to_treat[1]) 
			request_to_treat = (first_point,second_point)
		for returned_info in query_handler(request_to_treat,receiver,self._data[receiver],sender,link_type):
			#print "In semantic(",algorithm,"): return",returned_info
			yield returned_info

	def successors(self,vertex_id):
		return self._graph.successors(vertex_id)
	def predecessors(self,vertex_id):
		return self._graph.predecessors(vertex_id)
	def parents(self,vertex_id):
		return self._data[vertex_id][Relations["c2p"]]
	def children(self,vertex_id):
		return self._data[vertex_id][Relations["p2c"]]
	def peers(self,vertex_id):
		return self._data[vertex_id][Relations["p2p"]]
	def relation(self,s_id,t_id):
		return self._links[(s_id,t_id)]
	def nodes(self):
		return self._graph.nodes()
	#def top(self):	
	#	ret  = []
	#	for x in self._graph.nodes():
	#		if len(self._data[x]["peers"]) > 0: ret.append(x)
	#	return ret	
	
	def degree_distrib(self):
		ret = [] 
		for x in self._graph.nodes_iter():
			deg = self._graph.out_degree(x)
			if deg == 0: continue
			ret.append(deg)
		ret.sort()
		ret.reverse()	
		return ret 	

	def split(self):
		neighbor = sets.Set() 
		nodes = dict()
		is_top = sets.Set()
		for x in self._graph.nodes_iter():
			if self._graph.out_degree(x) == 0:
				neighbor.add(x)
				continue
			parent_list = []
			child_list = []
			for neighbo in self._graph.successors_iter(x):
				if self._graph.out_degree(neighbo) == 0: continue
				rel =  self._links[(x,neighbo)]
				if rel == "c2p": parent_list.append(neighbo)
				elif rel == "p2c": child_list.append(neighbo)
			nodes[x] = (parent_list,child_list)
		local_top = sets.Set() 
		for x,tab in nodes.items():
			parent_list,child_list = tab
			if len(parent_list) == 0: local_top.add(x)
		#-------------------------
		#print "graph.neighbors",neighbor
		subgraph1 = sets.Set()
		subgraph2 = sets.Set()
		node_to_choice = dict()
		while len(local_top) == 1:
			#print "graph.single_top",local_top
			top_alone = local_top.pop()
			subgraph1.add(top_alone)
			node_to_choice[top_alone] = 1
			for x in nodes[top_alone][1]:
				if x in neighbor: continue
				local_top.add(x)
			if len(local_top) > 1: break
		#print "graph.local_top",local_top
		one = False
		starting_one = sets.Set()
		starting_two = sets.Set()
		for no in local_top:
			if one:
				subgraph1.add(no)
				starting_one.add(no)
				node_to_choice[no] = 1
				one = False
			else:
				subgraph2.add(no)
				starting_two.add(no)
				node_to_choice[no] = 2
				one = True
		#print "1:",subgraph1,"2:",subgraph2
		node_to_local_top = dict()
		for ltnode in local_top:
			to_visit = sets.Set()	
			to_visit.add( ltnode )
			while len(to_visit) > 0:
				element = to_visit.pop()
				if not node_to_local_top.has_key(element): node_to_local_top[element] = sets.Set()
				node_to_local_top[element].add(node_to_choice[ltnode])
				child_list = nodes[element][1]
				for child in child_list:
					if child in neighbor: continue
					to_visit.add( child )
		todel = []
		#print "classify",node_to_local_top	
		for no,li in node_to_local_top.items():
			if len(li) == 1:	
				choice = li.pop()
				if choice == 1:
					subgraph1.add(no)
				else:
					subgraph2.add(no)
				todel.append(no)
		for no in todel: del node_to_local_top[no]
		#print "tie_break",node_to_local_top	
		for no in node_to_local_top.keys():
			subgraph1.add(no)
		#print "1:",subgraph1,"2:",subgraph2
		return subgraph1,subgraph2
	def degree_distribution(self):
		ret = dict()
		selector = { "c2p":"parents","p2c":"children","p2p":"peers"}
		for x in self._graph.nodes_iter():
			if self._graph.out_degree(x) == 0: continue
			count = { "peers":0,"parents":0,"children":0}
			for n in self.sucessors(x):
				link = (x,n)
				relation = self._links[link]
				count[selector[relation]] += 1 
			ret[x] = count
		return ret  
